1566. Пирог Жоры

Жора на праздник пригласил гостей, p из которых прибыли вовремя, а a задержались. Для того чтобы занять гостей, он попытался поиграть с ними в командные игры, но быстро обнаружил, что р гостей невозможно разделить на любое количество одинаковых по размеру групп, состоящих из более чем одного человека.

К счастью, у него оказался запасной план – торт, которым он хотел поделиться с друзьями. Торт имеет форму квадрата, и Жора настаивал на том, чтобы разрезать его на равные квадратные кусочки. Он хочет зарезервировать один кусочек для каждого из отсутствующих друзей, а остальные разделить поровну между р прибывших гостей. Себе кусочка он не оставляет. Сможет ли Жора таким образом поделить торт?

Вход. Состоит из нескольких тестов. Каждый тест состоит из одной строки, содержащей неотрицательное число a и положительное число p, удовлетворяющие выше описанным условиям. Оба числа a и p являются 32-битовыми знаковыми целыми числами. Последняя строка содержит "-1 -1" и не обрабатывается.

Выход. Для каждого теста в отдельной строке вывести "Yes" если торт можно поделить указанным образом и "No" иначе.

Пример входа

1 3
1024 17
2 101
0 1
-1 -1

Пример выхода

Yes

Yes

No

Yes

РЕШЕНИЕ

теория чисел - квадратические вычеты

Анализ алгоритма

Пусть торт было разрезано на n² частей. Обозначим через k количество кусочков торта, которое досталось p гостям. Тогда a + kp = n², откуда n² º a (mod p). Последнее уравнение имеет решение тогда и только тогда, когда число a есть квадратическим вычетом по простому модулю p. То есть символ Лежандра равен 1.

Критерий Эйлера. Число a, которое не делится на непарное простое p, является квадратическим вычетом по модулю p тогда и только тогда, когда º 1 (mod p), и квадратическим невычетом, если º -1 (mod p).

Из критерия Эйлера следует, что = = 1, = 0. То есть числа 0 и 1 являются квадратическими вычетами по любому простому модулю p. Если a º b (mod p), то = . Если входное значение a > p, то число a можно уменьшить, положив a = a mod p.

Для решения задачи достаточно вычислить символ Лежандра º (mod p). Если он равен 1, то вывести Yes, иначе No.

Пример

Для первого теста имеем уравнение n² º 1 (mod 3), которое имеет решение n = 1. Для третьего теста получим уравнение n² º 2 (mod 101), которое не имеет решений, так как = (mod 101) º 2⁵⁰ (mod 101) º -1.

Реализация алгоритма

Функция power вычисляет a^k mod n с временной оценкой O(log k). Поскольку в функции power следует умножать 32 - битовые числа, то во избежание потерь данных заведем 64 - битовые числа res и x.

int power(int a, int k, int n)

{

long long res = 1, x = a;

while(k > 0)

{

if (k & 1) res = res * x % n;

k >>= 1;

x = x * x % n;

}

return (int)res;

}

Читаем входные значения a и p. Положим a = a mod p (если этого не сделать – получим Time Limit). Если значение a равно 0 или 1 то ответ Yes, иначе по формуле вычисляем символ Лежандра. В соответствии с его значением выводим ответ.

while(scanf("%d %d",&a,&p) == 2, a + p > 0)

{

a = a % p;

if (!a || (a == 1)) res = 1;

else res = power(a,(p - 1) / 2,p);

if (res == 1) printf("Yes\n");

else printf("No\n");

}